package codeTop;

import java.util.PriorityQueue;

public class q215 {

    //回家等通知写法
    public int findKthLargest1(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i = 0; i < k; i++) {
            queue.add(nums[i]);
        }
        for (int i = k; i < nums.length ; i++) {
            queue.add(nums[i]);
            queue.poll();
        }
        return queue.peek();
    }

    //类快排写法，这个不用回家等通知了
    public int findKthLargest(int[] nums, int k) {
        return quickFind(nums,k,0, nums.length-1);
    }

    public int quickFind(int[] nums,int k,int low,int high){
        if (low < high) {
            int partition = partition(nums, low, high);
            if (partition == nums.length - k) {
                return nums[partition];
            }
            if (partition < nums.length - k) {
                return quickFind(nums,k,partition+1,high);
            }
            return quickFind(nums,k,low,partition-1);
        }
        return nums[low];
    }

    public int partition(int[] nums,int low,int high){
        int pivot = nums[low];
        while (low < high) {
            while (low < high && nums[high] >= pivot) {
                high--;
            }
            nums[low] = nums[high];
            while (low < high && nums[low] <= pivot) {
                low++;
            }
            nums[high] = nums[low];
        }
        nums[low] = pivot;
        return low;
    }

    public static void main(String[] args) {
        q215 q = new q215();
        q.findKthLargest(new int[]{3,2,3,1,2,4,5,5,6},4);
    }

}
